package leetcode.year2021.month10;

import java.util.LinkedList;
import java.util.List;

/**
 * 148. 排序链表
 */
public class _30_02SortList148 {
  public static void main(String[] args) {
  }

  public ListNode sortList(ListNode head) {
    return sortListByMerge(head, null);
  }

  private ListNode sortListByMerge(ListNode head, ListNode tail) {
    if (head == null){
      return head;
    }
    if (head.next == tail){
      head.next = null;
      return head;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != tail){
      slow = slow.next;
      fast = fast.next;
      if (fast != tail){
        fast = fast.next;
      }
    }
    ListNode mid = slow;
    ListNode left = sortListByMerge(head, mid);
    ListNode right = sortListByMerge(mid, tail);
    return mergeTwoSortedList(left,right);
  }

  private ListNode mergeTwoSortedList(ListNode list1, ListNode list2){
    ListNode dummy = new ListNode(-1);
    ListNode temp = dummy;
    while (list1 != null && list2 != null){
      if (list1.val > list2.val){
        temp.next = list2;
        list2 = list2.next;
        temp = temp.next;
        temp.next = null;
      } else {
        temp.next = list1;
        list1 = list1.next;
        temp = temp.next;
        temp.next = null;
      }
    }
    if (list1 != null){
      temp.next = list1;
    }
    if (list2 != null){
      temp.next = list2;
    }
    return dummy.next;
  }

//  // 归并排序
//  public ListNode sortList(ListNode head) {
//    return sortListByMerge(head, null);
//  }
//
//  private ListNode sortListByMerge(ListNode head, ListNode tail) {
//    if (head == null) {
//      return head;
//    }
//    if (head.next == tail){
//      head.next = null;
//      return head;
//    }
//    ListNode slow = head;
//    ListNode fast = head;
//
//    while (fast != tail) {
//      slow = slow.next;
//      fast = fast.next;
//      if (fast != tail) {
//        fast = fast.next;
//      }
//    }
//
//    ListNode mid = slow;
//    ListNode list1 = sortListByMerge(head,mid);
//    ListNode list2 = sortListByMerge(mid,tail);
//    return merge(list1,list2);
//  }
//
//
//  public ListNode merge(ListNode head1, ListNode head2) {
//    ListNode dummyHead = new ListNode(0);
//    ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
//    while (temp1 != null && temp2 != null) {
//      if (temp1.val <= temp2.val) {
//        temp.next = temp1;
//        temp1 = temp1.next;
//      } else {
//        temp.next = temp2;
//        temp2 = temp2.next;
//      }
//      temp = temp.next;
//    }
//    if (temp1 != null) {
//      temp.next = temp1;
//    } else if (temp2 != null) {
//      temp.next = temp2;
//    }
//    return dummyHead.next;
//  }

  // 该解法超出时间限制
//  public static ListNode sortList(ListNode head) {
//    // 思路：维护一个新的链表
//    ListNode newHead = null;
//
//    while (head != null){
//      ListNode tempHead = head.next;
//      head.next = null;
//      if (newHead == null){
//        newHead = head;
//      } else {
//        newHead = insertNodeIntoSortedList(newHead, head);
//      }
//      head = tempHead;
//    }
//
//    return newHead;
//
//  }
//
//  private static ListNode insertNodeIntoSortedList(ListNode list, ListNode entry) {
//    ListNode resultHead = list;
//    if (entry.val < list.val){
//      entry.next = list;
//      resultHead = entry;
//      return resultHead;
//    }
//    while (list.next != null){
//      if (list.next.val > entry.val){
//        ListNode temp = list.next;
//        list.next = entry;
//        entry.next = temp;
//        return resultHead;
//      }
//      list = list.next;
//    }
//    list.next = entry;
//    return resultHead;
//  }


  public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


  /**
   * 148. 排序链表
   * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
   *
   * 进阶：
   *
   * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
   *
   *
   * 示例 1：
   *
   *
   * 输入：head = [4,2,1,3]
   * 输出：[1,2,3,4]
   * 示例 2：
   *
   *
   * 输入：head = [-1,5,3,4,0]
   * 输出：[-1,0,3,4,5]
   * 示例 3：
   *
   * 输入：head = []
   * 输出：[]
   *
   *
   * 提示：
   *
   * 链表中节点的数目在范围 [0, 5 * 104] 内
   * -105 <= Node.val <= 105
   */
}
